package com.lw.leetcode.back.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 2192. 有向无环图中一个节点的所有祖先
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/8 11:58
 */
public class GetAncestors {

    public static void main(String[] args) {
        GetAncestors test = new GetAncestors();

        // {{},{},{},{0,1},{0,2},{0,1,3},{0,1,2,3,4},{0,1,2,3}}
//        int[][] arr = {{0, 3}, {0, 4}, {1, 3}, {2, 4}, {2, 7}, {3, 5}, {3, 6}, {3, 7}, {4, 6}};
//        int n = 8;

        // {{},{0},{0,1},{0,1,2},{0,1,2,3}}
        int[][] arr = {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}};
        int n = 5;

        List<List<Integer>> ancestors = test.getAncestors(n, arr);
        System.out.println(ancestors);
    }

    private Set<Integer> head = new HashSet<>();
    private List<Set<Integer>> values = new ArrayList<>();
    private Map<Integer, List<Integer>> map = new HashMap<>();

    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        int[] arr = new int[n];
        for (int[] edge : edges) {
            arr[edge[1]] = 1;
            map.computeIfAbsent(edge[1], v -> new ArrayList<>()).add(edge[0]);
        }
        for (int i = 0; i < n; i++) {
            if (arr[i] == 0) {
                head.add(i);
            }
        }
        for (int i = 0; i < n; i++) {
            values.add(new HashSet<>());
        }
        for (int i = 0; i < n; i++) {
            find(i);
        }
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List<Integer> li = new ArrayList<>(values.get(i));
            Collections.sort(li);
            list.add(li);
        }
        return list;
    }

    private Set<Integer> find(int v) {
        Set<Integer> set = values.get(v);
        if (head.contains(v) || !set.isEmpty()) {
            return set;
        }
        for (Integer index : map.get(v)) {
            set.addAll(find(index));
        }
        set.addAll(map.get(v));
        return set;
    }

}
